/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/nth-digit
   @Language: C++
   @Datetime: 19-05-23 12:51
   */

class Solution {
public:
	/**
	 * @param n: a positive integer
	 * @return: the nth digit of the infinite integer sequence
	 */
	int findNthDigit(int n) {
		// write your code here
		if(n<10) return n;
		const int bits[]={9,180,2700,36000,450000,5400000,63000000,720000000,INT_MAX};
		int bit=0;
		for(; n>bits[bit]; n-=bits[bit++]);
		int r=n%(bit+1);
		int k=n/(bit+1)+(r?0:-1);
		char str[32];
		sprintf(str,"%d",(int)pow(10,bit)+k);
		return str[r?r-1:bit]-'0';
	}
};
